package 美团;

import java.util.Stack;

public class _151_翻转字符串里的单词 {
    // 方法一：写一个由于翻转数组的方法
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;
        // 先去掉多余的空格
        StringBuilder sb = trimSpaces(s);
        String remove_more_zero = sb.toString();
        char[] arr = remove_more_zero.toCharArray();
        reverse(arr, 0, arr.length);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == ' ') continue;
//            int begin = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] == ' ') {
                    reverse(arr, i, j);
                    i = j + 1;
                    break;
                }
            }
        }
        return new String(arr);
    }

    private void reverse(char[] arr, int begin, int end) {
        int left = begin, right = end - 1;
        while (left <= right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    // 方法二：利用栈
    public String reverseWords2(String s) {
        if (s == null || s.length() == 0) return s;
        Stack<String> stack = new Stack<>();
        char[] arr = s.toCharArray();
        int index = 0;

        while (index < arr.length) {
            if (arr[index] != ' ') {
                int end = index;
                while (end < arr.length) {
                    if (arr[end] != ' ') {
                        end++;
                    } else {
                        break;
                    }
                }
                String str = new String(arr, index, end - index);
                stack.push(str);
                index = end + 1;
            } else {
                index++;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            if (stack.size() != 1) {
                sb.append(stack.pop() + " ");
            } else {
                sb.append(stack.pop());
            }
        }
        return sb.toString();
    }

}
